This section is intended to introduce the reader to various aspects of art, which may be related to various aspects of the present invention that are described and/or claimed below. This discussion is believed to be helpful in providing the reader with background information to facilitate a better understanding of the various aspects of the present invention. Accordingly, it should be understood that these statements are to be read in this light, and not as admissions of prior art.
It is well known in the field of cryptography that implementations of exponentiation algorithms need to be resistant against side channel attacks. It has for example been shown that RSA private keys can be retrieved by observing the power consumption of the microprocessor that executes the algorithm—see P. Kocher, J. Jaffe, and B. Jun. “Differential Power Analysis”. In M. J. Wiener, editor, Advances in Cryptology CRYPTO '99, volume 1666 of Lecture Notes in Computer Science, pages 388-397, Springer-Verlag, 1999.
These so-called Simple Power Attacks (SPA) target basic exponentiation algorithm based on the square and multiply technique. A first countermeasure was to make sure that a squaring operation is always followed by a multiplication, no matter the value of the bit of the exponent. In this case, the multiplication is sometimes a fake multiplication. This is known as the square and multiply always algorithm—see C. Clavier and M. Joye. “Universal Exponentiation Algorithm”. In . K. Ko, D. Naccache, and C. Paar, editors, Cryptographic Hardware and Embedded Systems—CHES 2001, volume 2162 of Lecture Notes in Computer Science, pages 300-308. An exemplary right-to-left algorithm is given by:
Input: x, d = (dl−1 , ..., d0)2Output: y = xdR[0] ←1; R[1] ←1 , R[2] ←x ,for i=0 to l−1if di=0 thenR[0] ← R[0] * R[2]; (fake multiplication)R[2] ← R[2]2 ;if di=1 thenR[1] ← R[1] * R[2];R[2] ← R[2]2 ;endreturn R[1]
It will be appreciated that the ‘mod N’ have been left out for reasons of clarity; this is the case throughout the description.
Another threat against cryptographic algorithms based on exponentiation are Fault Attacks (FA) that introduce random errors during execution of the algorithm in the hope of gleaning useful information from the result.
Several techniques have been proposed to mitigate this attack. A first solution is to perform the exponentiation twice and compare the results. A second solution, described in WO 98/52319, is to use the public exponent e associated to d to check that the result is correct before it is output.
These solutions are however costly and more efficient techniques have been proposed. In particular, Boscher, Naciri and Prouff provide a more efficient method that provides an implementation resistant against both SPA and FA—see Arnaud Boscher, Robert Naciri, and Emmanuel Prouff. CRT RSA Algorithm Protected against Fault Attacks. In D. Sauveron et al., editors, Information Security Theory and Practices (WISTP 2007), volume 4462 of Lecture Notes in Computer Science, pages 229-243, Springer-Verlag, 2007.
Input: x, d = (dl−1 , ..., d0)2Output: y = xdR[0] ←1; R[1] ←1 , R[2] ← x ,for i=0 to l−1if di=0 thenR[0] ← R[0] * R[2]; (SPA protection )R[2] ← R[2]2 ;if di=1 thenR[1] ← R[1] * R[2];R[2] ← R[2]2 ;endif R[2] ≠ R[0] * R[1] * x then return ‘error’ (FA protection )return R[1]
The algorithm relies on the observation that the ratio between R[2] and R[0] times R[1] is always equal to the base input x at each iteration of the algorithm. Thus, verifying before the output that R[2]=R[0]*R[1]*x is sufficient to counter fault attacks.
A generalised version, right-to-left m-ary exponentiation has been proposed by Andrew Chi-Chih Yao in “On the Evaluation of Powers”. SIAM J. Comput., 5(1):100-103, 1976. The algorithm is vulnerable to SPA as an attacker is able to detect when a zero bit in the exponent is treated. To counter this, a fake multiplication is generally added when the bit exponent is zero. Such an algorithm is said SPA-resistant and is illustrated below. This algorithm requires m+1 registers in memory to compute xd.
Input: x, d = (dl−1 , ..., d0)mOutput: y = xdfor i=0 to m−1R[i] ←1endR[m] ← xfor i=0 to l−2if di=0 thenR[0] ← R[0] * R[m]; (SPA protection)R[m] ← R[m]m ;if di=1 thenR[1] ← R[1] * R[m];R[m] ← R[m]m ;...if di=m−1 thenR[m−1] ← R[m−1] * R[m];R[m] ← R[m]m ;endR[dl−1] ← R[dl−1] * R[m];R[m−1] ← R[1] * R[2]2 * R[3]3 * ... * R[m−1]m−1return R[m−1]
Yoo-Jin Baek has generalized the method from to Boscher, Naciri and Prouff, in a recent paper “Regular 2w-ary right-to-left exponentiation algorithm with very efficient DPA and FA countermeasures.” International Journal of Information Security, 9(5):363-370, 2010, where he shows how Yao's algorithm can be adapted to resist against fault attacks. The coherence check between the different values involved in the computation is based on the following relation:
if R[m]*x≠(R[0]*R[1]*R[2]* . . . * R[m−1])m−1 then return ‘error’
Although the previous techniques are efficient in term of computation, they are not well suited for memory-constrained environments. It can therefore be appreciated that there is a need for a solution that provides an attack-resistant exponentiation algorithm suitable for memory-constrained devices. This invention provides such a solution.